package backdate;

import java.util.*;

//https://leetcode.cn/leetbook/read/illustration-of-algorithm/5dfv5h/
//某店铺将用于组成套餐的商品记作字符串 goods，其中 goods[i] 表示对应商品。请返回该套餐内所含商品的 全部排列方式 。
//返回结果 无顺序要求，但不能含有重复的元素。
public class LCR_157套餐内商品的排列顺序 {
    class Solution {
        List<String> res = new LinkedList<>();
        char[] arr;
        public String[] goodsOrder(String goods) {
            arr = goods.toCharArray();
            dfs(0);
            return res.toArray(new String[res.size()]);
        }
        void dfs(int x){
            if(x == arr.length - 1){
                res.add(String.valueOf(arr));
                return;
            }
            HashSet<Character> set = new HashSet<>();
            for(int i=x; i<arr.length; i++){
                if(set.contains(arr[i])) continue;
                set.add(arr[i]);
                swap(i,x);
                dfs(x+1);
                swap(i,x);
            }
        }
        void swap(int i, int x){
            char tmp = arr[i];
            arr[i] = arr[x];
            arr[x] = tmp;
        }
    }
    //回溯
    class Solution2 {
        List<String> rec;
        boolean[] vis;

        public String[] goodsOrder(String goods) {
            int n = goods.length();
            rec = new ArrayList<String>();
            vis = new boolean[n];
            char[] arr = goods.toCharArray();
            Arrays.sort(arr);
            StringBuffer perm = new StringBuffer();
            backtrack(arr, 0, n, perm);
            int size = rec.size();
            String[] recArr = new String[size];
            for (int i = 0; i < size; i++) {
                recArr[i] = rec.get(i);
            }
            return recArr;
        }

        public void backtrack(char[] arr, int i, int n, StringBuffer perm) {
            if (i == n) {
                rec.add(perm.toString());
                return;
            }
            for (int j = 0; j < n; j++) {
                if (vis[j] || (j > 0 && !vis[j - 1] && arr[j - 1] == arr[j])) {
                    continue;
                }
                vis[j] = true;
                perm.append(arr[j]);
                backtrack(arr, i + 1, n, perm);
                perm.deleteCharAt(perm.length() - 1);
                vis[j] = false;
            }
        }
    }
    //下一个排列
    class Solution3 {
        public String[] goodsOrder(String goods) {
            List<String> ret = new ArrayList<String>();
            char[] arr = goods.toCharArray();
            Arrays.sort(arr);
            do {
                ret.add(new String(arr));
            } while (nextPermutation(arr));
            int size = ret.size();
            String[] retArr = new String[size];
            for (int i = 0; i < size; i++) {
                retArr[i] = ret.get(i);
            }
            return retArr;
        }

        public boolean nextPermutation(char[] arr) {
            int i = arr.length - 2;
            while (i >= 0 && arr[i] >= arr[i + 1]) {
                i--;
            }
            if (i < 0) {
                return false;
            }
            int j = arr.length - 1;
            while (j >= 0 && arr[i] >= arr[j]) {
                j--;
            }
            swap(arr, i, j);
            reverse(arr, i + 1);
            return true;
        }

        public void swap(char[] arr, int i, int j) {
            char temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }

        public void reverse(char[] arr, int start) {
            int left = start, right = arr.length - 1;
            while (left < right) {
                swap(arr, left, right);
                left++;
                right--;
            }
        }
    }
}
